package com.example.slidingwindow;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 *  注意：
 *  对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 *  如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 *  示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 *
 *  示例 2：
 * 输入：s = "a", t = "a"
 * 输出："a"
 *
 *  示例 3:
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 */
public class Leetcode76_MinWindow {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";

        s = "abc";
        t = "cba";

        System.out.println(new Solution().minWindow(s, t));
    }

    static class Solution {
        /**
         * 滑动窗口
         * 当窗口没有包含 t 中所有的元素，窗口右边界+1
         * 当窗口已经包含 t 中所有的元素(当前窗口为可行窗口)，窗口左边界+1(尝试缩小可行窗口是否还是可行的窗口)
         * @param s
         * @param t
         * @return
         */
        public String minWindow2(String s, String t) {
            if (s.length() < t.length() || s.length() == 0 || t.length() == 0) return "";
            char[] sArray = s.toCharArray();
            char[] tArray = t.toCharArray();
            int sLen = sArray.length;
            int tLen = tArray.length;
            Map<Character, Integer> sourceMap = new HashMap<>();// 存放t中元素和对应的次数
            Map<Character, Integer> window = new HashMap<>();// 当前窗口存放的元素和对应的次数
            // 初始统计t中出现的元素和对应的次数
            for (int i = 0; i < tLen; i++) {
                int v = sourceMap.getOrDefault(tArray[i], 0) + 1;
                sourceMap.put(tArray[i], v);
            }

            int left = 0, right = -1; // 初始窗口左右边界
            int resLeft = -1, resRight = -1;
            int len = Integer.MAX_VALUE;// 记录可行窗口的长度
            while (right < sLen) {
                ++right;
                if (right < sLen && sourceMap.containsKey(sArray[right])) {
                    int v = window.getOrDefault(sArray[right], 0) + 1;
                    window.put(sArray[right], v);
                }

                while (isWinContainAllSourceStr(sourceMap, window) && left <= right) {
                    if (right - left + 1 < len) { // 只有当可行窗口的长度比之前的长度小时才需要更新可行窗口的左右边界
                        len = right - left + 1;
                        resLeft = left;
                        resRight = left + len;
                    }

                    if (sourceMap.containsKey(sArray[left])) {
                        int newVal = window.getOrDefault(sArray[left], 0) - 1;
                        window.put(sArray[left], newVal);
                    }

                    ++left;
                }
            }

            return resLeft == -1 ? "" : s.substring(resLeft, resRight);
        }


        /**
         * 暴力法，从t.length的子串开始逐个匹配看是否有子串可以包含t中所有的字符(hashtable)
         * @param s
         * @param t
         * @return
         */
        private String minWindow1(String s, String t) {
            if (s.length() < t.length() || s.length() == 0 || t.length() == 0) return "";
            char[] sArray = s.toCharArray();
            char[] tArray = t.toCharArray();
            int sLen = sArray.length;
            int tLen = tArray.length;

            Map<Character, Integer> map = new HashMap<>();// key 为 s的每个字符，value为s每个字符出现的次数
            for (char c : tArray) {
                Integer v = map.getOrDefault(c, 0);
                map.put(c, ++v);
            }

            for (int i = tLen; i <= sLen; i++) {
                for (int start = 0; start <= sLen - i; start++) {
                    if (isWinContainAllSourceStr(sArray, start, start + i - 1, tArray))
                        return s.substring(start, start + i);
                }
            }
            return "";
        }

        /**
         * 判断当前 window 是否已经包含了sourceMap的所有元素
         *
         * @param sourceMap
         * @param window
         * @return
         */
        private boolean isWinContainAllSourceStr(Map<Character, Integer> sourceMap, Map<Character, Integer> window) {
            Iterator<Map.Entry<Character, Integer>> iterator = sourceMap.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Character, Integer> next = iterator.next();
                Character key = next.getKey();
                Integer value = next.getValue();
                if (window.getOrDefault(key, 0) < value) return false;
            }
            return true;
        }

        /**
         * 判断所给字符数组从start到end(包含end)是否包含targets中的所有元素
         * @param chars
         * @param start
         * @param end
         * @param targets
         * @return
         */
        private boolean isWinContainAllSourceStr(char[] chars, int start, int end, char[] targets) {
            // 构建一个从start到end这个区间的map (key: 区间每个出现的字符, value为该字符出现的次数)
            Map<Character, Integer> map = new HashMap<>();
            for (int i = start; i <= end; i++) {
                int v = map.getOrDefault(chars[i], 0);
                map.put(chars[i], ++v);
            }

            // 遍历targets 看start到end是否包含targets中的所有元素
            for (int i = 0; i < targets.length; i++) {
                int v = map.getOrDefault(targets[i], 0);
                System.out.println(targets[i]);
                System.out.println(map);
                if (v == 0){
                    return false;
                } else {
                    map.put(targets[i], --v);
                }
                System.out.println(map);
            }
            return true;
        }

        public String minWindow(String s, String t) {
            return minWindow2(s, t);
        }
    }
}
